1. Field of the Invention
The invention relates to an apparatus and a method for controlling colors printed by a printer or displayed on a monitor to reduce the visibility of error diffusion dot patterns, and more particularly, to an apparatus and method for performing vector error diffusion with output color control.
2. Description of the Related Art
Reproduction and display of continuous tone images on color monitors and color printers using spatial grayscale or halftoning techniques is well known. However, the resulting halftone images display various amounts or levels of "graininess" resulting from error inherent in the halftoning process.
Digital halftoning is the process of converting a continuous tone image to bi-level. Many output devices, including many printers and some CRT (cathode ray tube) and LCD (liquid crystal display) based devices are intrinsically bi-level, that is, the process can only print or display a dot or no dot. Thus, a variety of geometrical patterns are created such that a group of dots and blank areas represent the continuous tone image as closely as possible. Because the halftoned image is only an approximate representation of the continuous tone image, there are differences between the continuous tone image and the halftone image. Those areas of the halftone pattern that do not match the original image are noise or error. An objective of much research in digital halftoning is reducing the amount of visible noise.
Digital halftoning can be classified into two classes: "conventional, passive halftoning" and "active halftoning;" with error diffusion being a widespread method of choice in the latter category. Conventional passive halftoning (discussed first) yields an appearance that is similar to that provided by classical analogue processes developed before digital techniques were available; it is most appropriate for devices that cannot display isolated pixels. Error diffusion produces an image appearance more like that created by the pointillist painters at around the end of the 19th century. It is most appropriate for devices that can display isolated pixels. Error diffusion tends to have noise at higher, and hence less visible spatial frequencies, often resulting in a more pleasing appearance, see for instance: "Threshold Modulation in Error Diffusion," by K. T. Knox and R. Eschbach, Journal of Electronic Imaging 3, pp. 185-192 (1993) and the references cited therein.
Several attempts have been made to reduce the sensitivity to process noise and maintain the appearance of the tonal gradation of the continuous tone image for conventional halftoning. For example, U.S. Pat. No. 4,625,222 to Bassettit et al. discloses a print enhancement control system for an electrostatic copier wherein control logic circuitry processes a set of image altering parameters to improve image production quality. These parameters have fixed or predetermined values and improve image quality by modifying modulated gray scale signals.
U.S. Pat. No. 4,700,229 to Hermann et al. discloses an image enhancement circuit which converts a low quality image signal into a high quality image signal by modifying the binary representation of a picture. Image enhancement is accomplished by multiplying a series of error difference signals by a series of weighting factors which produce clearer images by improving apparent picture resolution.
U.S. Pat. No. 4,672,463 to Tomohisa et al. discloses a method of improving image quality within an electrostatic reproduction machine wherein the sharpness of an image is improved based on the value of an image sharpness control parameter that has been calculated by examining the copy quality of an original.
U.S. Pat. No. 4,709,250 to Takeuchi discloses an image forming apparatus which improves the halftone image quality of an original. The pulse width of a reference control signal controls and improves image quality in response to detected image density signals.
U.S. Pat. No. 4,724,461 to Rushing discloses an image improving process control for an electrostatic copying machine which maintains high image quality by adjusting a set of process control parameters.
U.S. Pat. No. 4,256,401 to Fujimura et al. discloses an image density adjustment method wherein a predetermined image density level within an electrostatic copying machine is maintained at the standard density by a varying set of input control parameters.
U.S. Pat. No. 4,693,593 to Gerger discloses a method of improving the image quality by controlling a single process parameter in response to changes in sensitometeric characteristics of an image transfer member.
As mentioned above, another way of converting from continuous tone to a bi-level representation is error diffusion as disclosed in an article entitled "An Adaptive Algorithm for Spatial Greyscale" by Robert W. Floyd and Louis Steinberg, Proc. Soc. Inf. Disp. 17, 75-77 (1976). The process of error diffusion involves an algorithm which determines whether or not to print a dot at a certain location based on a comparison of the continuous tone data with a threshold value. Gray levels above a chosen threshold are assigned a dot to be printed and those below the threshold are not assigned a dot to be printed. If the threshold corresponds to midway between black and white, the method always chooses the closer of black and white. The inherent error resulting from such a choice is propagated in specified amounts to adjacent picture elements or pixels not yet considered to change the pixels prior to thresholding. This method produces a more accurate representation of a gray tone over a small area encompassing several dots than conventional halftoning. Hence, the error in the intensity of the digital image is diffused and, on average, zero.
The fraction of the error added to each neighhour depends on a set of weights, the total error being multiplied by the weight corresponding to a given neighhour and then added to the value of that neighhour. The choice of weight can greatly affect the image quality, and much has been said about weights appropriate for giving pleasing results. Three examples of weights other than those in the original Floyd and Steinberg algorithm may be found in papers by Jarvis, Judice, and Ninkey ("A Survey of Techniques for Display of Continuous-Tone Pictures on Bilevel Displays", Computer Graphics and Image Processing, 5, pp. 13-40, 1976), Stucki, ("Image Processing for Document Reproduction", Advances in Digital Image Processing, pp. 177-218, New York, Plenum, 1979), and Fan, ("A Simple Modification of Error Diffusion Weights", Proceedings of the IS&T 46th Annual Conference, pp. 113-114, Boston 1993).
Other attempts at reducing the patterns visible include changing the order in which pixels are considered. This can be as simple as changing direction on each scanline, as suggested by Floyd and Steinberg in their original article, or it can involve following a complicated curve. The latter method has been described in various forms including papers by Cole ("Naive Halftoning", Proceedings of CGI'90, Springer-Verlag, pp. 203-222), and Wyviil and McNaughton ("Three Plus Five Makes Eight: A Simplified Approach to Halftoning", Proceedings of CGI'91, Springer Verlag, pp. 379-394).
A variation of the Floyd and Steinberg error diffusion algorithm involves using a varying threshold to determine whether to print or display a dot. Examples of these varying threshold algorithms are: C. Billotet-Hoffmann and O. Bryngdahl, "On the Error Diffusion Technique for Electronic Halftoning", Proc. Soc. Inf. Disp. 24, pp. 253-258 (1983), in which a dither pattern was used as a threshold; U.S. Pat. No. 5,045,952 to Eschbach in which a function of the input signal was used as the threshold; and U.S. Pat. No. 5,055,942 to Levien in which a function of the binary output was used as the threshold.
Other known processes for performing error diffusion of color images include prior art devices that separately diffuse the error associated with each color. For example, in performing error diffusion of an RGB image, the prior art algorithms separately diffuse red while ignoring green and blue. Such an algorithm does not consider the effects of interactions between dot patterns of different color components comprising a color image. Other prior art algorithms perform separate error diffusion for each color of a RGB image but also perform color conversion from RGB to CMYK.
What is known as vector error diffusion was described in a paper by Dennis Venable, Judy Stinehour and Paul Roetling ("Selection and Use of Small Color Sets for Pictorial Display", Proc IS&T Annual Meeting, Rochester 1990) and in a paper by R. Miller and J. Sullivan ("Color Halftoning Using Error Diffusion and a Human Visual System Model", Proc IS&T Annual Meeting, Rochester 1990). In vector error diffusion colors are treated as points in a three dimensional space, with the colors printable or displayable at a given pixel discrete locations within that space. When a continuous tone color is to be displayed, the closest displayable color is selected, and the error is calculated as a vector in color space. Here, the "closeness" might be the simple distance in color space or a weighted distance based on the human visual model. The vector is the difference between the desired color and the available color. The (vector) error is then diffused in the same way as in normal error diffusion.